package com.zklh.leetcode.top100.problem101;

import com.zklh.leetcode.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Solution2 {

    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> leftQueue = new LinkedList<>();
        Queue<TreeNode> rightQueue = new LinkedList<>();

        leftQueue.add(root.left);
        rightQueue.add(root.right);

        TreeNode leftPointer = null;
        TreeNode rightPointer = null;

        while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
            leftPointer = leftQueue.poll();
            rightPointer = rightQueue.poll();

            if (leftPointer == null && rightPointer == null) {
                continue;
            } else if (leftPointer != null && rightPointer != null) {
                if (leftPointer.val != rightPointer.val) {
                    return false;
                }
                leftQueue.add(leftPointer.left);
                leftQueue.add(leftPointer.right);
                rightQueue.add(rightPointer.right);
                rightQueue.add(rightPointer.left);
            } else {
                return false;
            }
        }

        return leftQueue.isEmpty() && rightQueue.isEmpty();
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);

        Solution2 solution2 = new Solution2();
        System.out.println(solution2.isSymmetric(root));
    }
}
